package com.chj.lintcode.backpack;

public class Code03_backpackIII {
	/**
	 * @param A: an integer array
	 * @param V: an integer array
	 * @param m: An integer
	 * @return: an array
	 */
	public static int backPackIII(int[] A, int[] V, int m) {
		if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) {
			return 0;
		}

		int[][] dp = new int[A.length + 1][m + 1];

		for (int i = 1; i <= A.length; i++) {
			for (int j = 1; j <= m; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j - A[i - 1] >= 0) {
					dp[i][j] = Math.max(dp[i][j], dp[i][j - A[i - 1]] + V[i - 1]);
				}
			}
		}

		return dp[A.length][m];
	}

	public static int backPackIII02(int m, int[] A, int[] V) {
		// write your code here
		if (A == null || A.length == 0 || V == null || V.length == 0) {
			return 0;
		}
		int n = A.length;
		int[][] dp = new int[n + 1][m + 1];
		dp[0][0] = 0;
		for (int i = 1; i <= m; i++) {
			dp[0][i] = -1;
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j >= A[i - 1] && dp[i][j - A[i - 1]] != -1) {
					dp[i][j] = Math.max(dp[i][j], dp[i][j - A[i - 1]] + V[i - 1]);
				}
			}
		}

		int res = 0;
		for (int i = 0; i <= m; i++) {
			if (dp[n][i] != -1) {
				res = Math.max(res, dp[n][i]);
			}
		}

		return res;
	}

//	http://buttercola.blogspot.com/2019/04/lintcode-440-backpack-iii.html
	public static void main(String[] args) {
		{
			int[] nums = { 2, 3, 5, 7 };
			int[] vs = { 1, 5, 2, 4 };
			int target = 10;
			System.out.println(backPackIII(nums, vs, target));
			System.out.println(backPackIII02(target, nums, vs));
		}

		{
			int[] nums = { 1, 2, 3 };
			int[] vs = { 1, 2, 3 };
			int target = 5;
			System.out.println(backPackIII(nums, vs, target));
			System.out.println(backPackIII02(target, nums, vs));
		}
	}
}
